import lombok.val;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ZhengDp
 * @Date 2023/4/6 5:22
 */
public class 哈希表_集合_映射 {

    @Test
    void test(){
        isAnagram("anagram"
                ,"nagaram");

    }
    /*
    * #problem 242 有效的字母异位词
    * */
    // 1. 利用HashMap
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < s.length();++i) {
            Character c = s.charAt(i);
            int sum = map.getOrDefault(c,0);
            sum++;
            map.put(c,sum);
        }
        for(int i =0;i<s.length();++i) {
            Character c = t.charAt(i);
            if(!map.containsKey(c)) {
                return false;
            }
            int sum = map.get(c);
            sum --;
            if(sum == 0) {
                map.remove(c);
            } else {
                map.put(c,sum);
            }
        }
        return map.isEmpty();
    }

    // 2. 数组映射即可
    public boolean isAnagram2(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        int[] mapper = new int[26];
        for(int i =0;i<s.length();++i) {
            Character c = s.charAt(i);
            ++mapper[c-'a'];
        }
        for(int i =0;i<s.length();++i) {
            --mapper[t.charAt(i) - 'a'];
        }
        for(int i =0;i<mapper.length;++i) {
            if(mapper[i] != 0) {
                return false;
            }
        }
        return true;
    }

    // 3.数组
    public boolean isAnagram3(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int[] mapper = new int[26];
        for(int i =0;i<s.length();++i) {
            ++mapper[s.charAt(i) - 'a'];
            --mapper[t.charAt(i) - 'a'];
        }
        for(int i =0;i<mapper.length;++i) {
            if(mapper[i] != 0) {
                return false;
            }
        }
        return true;
    }

    /*
    * #problem 49. 字母异位词分组
    * */
    // 1. 暴力解 ==> 超时
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        for(int i =0;i<strs.length;++i) {
            String word = strs[i];
            if(word == null) {
                continue;
            }
            // 找到word的所有同位词
            List<String> temp = new ArrayList<>();
            temp.add(word);
            char[] wordArray = word.toCharArray();
            for(int j =0; j < strs.length;++j) {
                if(i==j) {
                    continue;
                }
                char[] chars = strs[j].toCharArray();
                Arrays.sort(chars);
                if(Arrays.equals(wordArray,chars)) {
                    temp.add(strs[j]);
                    strs[j] = null;
                }
            }
            result.add(temp);
        }
        return result;
    }

    // 2. 排序 + HashMap
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String , List<String>> map = new HashMap<>();
        for(int i =0;i<strs.length;++i) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = Arrays.toString(chars);
            List<String> arrays = map.getOrDefault(key, new ArrayList<>());
            arrays.add(strs[i]);
            map.put(key,arrays);
        }
        List<List<String>> result = new ArrayList<>();
        map.forEach((key,val) -> {
            result.add(val);
        });
        return result;
    }

    public List<List<String>> groupAnagrams3(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            return Arrays.toString(chars);
        })).values());
    }

    // 3. 构建key
    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(int i =0; i<strs.length;++i) {
            String word = strs[i];
            int[] count = new int[26];
            for(int j =0;j<word.length();++i) {
                ++count[word.charAt(j) - 'a'];
            }
            StringBuilder str = new StringBuilder();
            for(int j=0;j<count.length;j++) {
                if(count[j] != 0) {
                    str.append('a' + j);
                    str.append(count[j]);
                }
            }
            String key = str.toString();
            List<String> arrays = map.getOrDefault(key,new ArrayList<>());
            arrays.add(word);
        }
        return new ArrayList<>(map.values());
    }

    /*
    * #problem 94 二叉树的中序遍历
    * */
    // 1. 递归
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        res.addAll(inorderTraversal(root.left));
        res.add(root.val);
        res.addAll(inorderTraversal(root.right));
        return res;
    }

    // 2. 迭代
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        // 用栈模拟递归操作
        while( p != null || !stack.isEmpty()) {
            // 左
            if(p != null) {
                stack.push(p);
                p = p.left;
            } else {
                // 根
                TreeNode cur = stack.pop();
                result.add(cur.val);
                // 右
                p = cur.right;
            }
        }
        return result;
    }

    /*
    * #problem 144. 二叉树的前序遍历
    * */
    // 1. 递归 根-左-右
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        res.add(root.val);
        res.addAll(preorderTraversal(root.left));
        res.addAll(preorderTraversal(root.right));
        return res;
    }

    // 2. 迭代
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            if(root != null ) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                root = cur.right;
            }
        }
        return res;
    }

    /*
    * #problem 145. 二叉树的后序遍历
    * */
    // 1. 递归 左-右-中
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null ) {
            return new ArrayList<>();
        }
        List<Integer> res = postorderTraversal(root.left);
        res.addAll(postorderTraversal(root.right));
        res.add(root.val);
        return res;
    }

    // 2. 迭代
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while( root != null || !stack.isEmpty()) {
            if( root != null ) {
                stack.push(root);
                root = root.left;
            } else {
                // 只有当其从右侧返回时，才将当前值插入到res中
                // 如何判断是从左侧返回还是右侧返回？
                root = stack.pop();
                // root.right == null ==> 说明 左右两侧都为null
                // 回溯到root节点，可以进行添加节点操作
                if(root.right == null || prev == root.right) {
                    res.add(root.val);
                    // 记录被处理过的根节点，避免重复处理
                    prev = root;
                    // root == null , 继续往上回溯
                    root = null;
                } else {
                    stack.push(root);
                    root = root.right;
                }
            }
        }
        return res;
    }

    /*
    * #problem 590. N 叉树的后序遍历
    * */
    // 1. 递归
    public List<Integer> postorder(Node root) {
        if(root == null) {
            return new ArrayList<>();
        }
        List<Node> children = root.children;
        List<Integer> res = new ArrayList<>();
        if(children != null ) {
            for(Node child : children) {
                res.addAll(postorder(child));
            }
        }
        res.add(root.val);
        return res;
    }

    // 2. 迭代
    public List<Integer> postorder1(Node root) {
        List<Integer> res = new ArrayList<>();
        Deque<Node> stack = new LinkedList<>();
        Map<Node,Integer> map = new HashMap<>();
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                List<Node> children = root.children;
                if(children != null && children.size() > 0 ) {
                    map.put(root,0);
                    root = children.get(0);
                } else {
                    root =null;
                }
            } else {
                // 回溯
                root = stack.peek();
                // 找到下一个孩子节点
                int index = map.getOrDefault(root,-1) + 1;
                List<Node> children = root.children;
                if(children != null && index < children.size()) {
                    map.put(root,index);
                    root = children.get(index);
                } else {
                    // 所有的孩子节点都已经遍历完毕
                    res.add(root.val);
                    map.remove(root);
                    root = null;
                }
            }
        }
        return res;
    }


}
